package com.csdemos.algs.graphs;

import java.util.Collections;
import java.util.LinkedList;

import com.csdemos.algs.PriorityQueue;
import com.csdemos.algs.sets.DisjointSet;

public class MST {
	
	public static class Edge implements Comparable<Edge>{
		int v1;
		int v2;
		int weight;
		
		public Edge(int v1, int v2, int weight) {
			super();
			this.v1 = v1;
			this.v2 = v2;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Edge o) {
			return weight - o.weight;
		}
		
		@Override
		public String toString() {
			return String.format("(%d, %d) - %d", v1, v2, weight);
		}
		
	}
	
	public static LinkedList<Edge> MST_Kruskal(Graph graph) {
		LinkedList<Edge> A = new LinkedList<Edge>();
		DisjointSet S = new DisjointSet();
		for (int v : graph.getVertexs()) {
			S.makeSet(v);
		}
		LinkedList<Edge> E = new LinkedList<Edge>();
		for (int v1 : graph.getVertexs()) {
			for (int v2 : graph.getAdjecents(v1)) {
				if (v1 < v2) {
					E.add(new Edge(v1, v2, graph.getWeight(v1, v2)));
				}
			}
		}
		Collections.sort(E);
		System.out.println(E.toString());
		for (Edge e : E) {
			int u = e.v1;
			int v = e.v2;
			if (S.findSet(u) != S.findSet(v)) {
				A.add(e);
				S.union(u, v);
			}
		}
		return A;
	}
	
	public static LinkedList<Edge> MST_Prim(Graph graph, int r) {
		int n = graph.getVertexs().length;
		LinkedList<Edge> A = new LinkedList<Edge>();
		int[] key = new int[n];
		int[] p = new int[n];
		for (int u : graph.getVertexs()) {
			key[u] = Integer.MAX_VALUE;
			p[u] = -1;
		}
		key[r] = 0;
		PriorityQueue Q = new PriorityQueue();
		Q.buildMinHeap(graph.getVertexs());
		while (!Q.isEmpty()) {
			int u = Q.heapExtractMin();
			for (int v : graph.getAdjecents(u)) {
				int w = graph.getWeight(u, v);
				if (Q.contains(v) && w < key[v]) {
					p[v] = u;
					key[v] = w;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			int v = i;
			if (v == r) {
				continue;
			}
			int pv = p[v];
			A.add(new Edge(v, pv, graph.getWeight(v, pv)));
		}
		return A;
	}

}
